package mashibing.class16;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 最短路径问题---Dijkstra算法详解（求顶点v1到其他各个顶点的最短路径）
 *
 * 练习LeetCode：743. 网络延迟时间
 */
public class Class16_6_Dijkstra {

    public static HashMap<Node, Integer> dijkstra1(Node from) {
        HashMap<Node, Integer> distinctMap = new HashMap<>();
        // 打过对号的点
        Set<Node> selectNode = new HashSet<>();

        distinctMap.put(from, 0);
        Node minNode = getMinNode(distinctMap, selectNode);
        while (minNode != null) {
            //  原始点  ->  minNode(跳转点)   最小距离distance
            Integer distinct = distinctMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!distinctMap.containsKey(toNode)) {
                    distinctMap.put(edge.to, distinct + edge.weight);
                } else {
                    distinctMap.put(edge.to, Math.min(distinctMap.get(toNode), distinct + edge.weight));
                }
            }
            selectNode.add(minNode);
            minNode = getMinNode(distinctMap, selectNode);
        }
        return distinctMap;
    }

    // 选择最小跳板路径，和不被选择过的节点
    public static Node getMinNode(HashMap<Node, Integer> distinctMap, Set<Node> selectNode) {
        Node minNode = null;
        int min = Integer.MAX_VALUE;
        for (Node node : distinctMap.keySet()) {
            Integer distinct = distinctMap.get(node);
            if (!selectNode.contains(node) && distinct < min) {
                minNode = node;
                min = distinct;
            }
        }
        return minNode;
    }
}
